package com.salim.leetcode.$15;

import java.util.*;

public class ThreeSum {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        Arrays.sort(nums);
        if(nums.length<3){
            return new ArrayList<>();
        }
        for(int x=0;x<nums.length-2;x++){
            if(x==0 ||nums[x] != nums[x-1]){
                int sum = -nums[x];
                int left = x+1;
                int right = nums.length-1;
                while (left<right){
                    if(nums[left]+nums[right]==sum){
                        result.add(Arrays.asList(nums[x],nums[left],nums[right]));
                        while (left<right && nums[left]==nums[left+1]){
                            left+=1;
                        }
                        while (right>left && nums[right-1]==nums[right]){
                            right-=1;
                        }
                        left+=1;
                        right-=1;
                    }else{
                        if(nums[left]+nums[right]>sum){
                            right-=1;
                        }else{
                            left+=1;
                        }
                    }
                }
            }
        }

        return result;
    }


    public static void main(String[] args){
        ThreeSum threeSum = new ThreeSum();
//        List<List<Integer>> result = threeSum.threeSum(new int[]{-1, 0, 1, 2, -1, -4});
//        for(List<Integer> it:result){
//            System.out.println(it+" ");
//        }


//        List<List<Integer>> result2 = threeSum.threeSum(new int[]{1,2,-2,-1});
//        for(List<Integer> it:result2){
//            System.out.println(it+" ");
//        }
//        List<List<Integer>> result3 = threeSum.threeSum(new int[]{1,1,-2});
//        for(List<Integer> it:result3){
//            System.out.println(it+" ");
//        }
//        List<List<Integer>> result4 = threeSum.threeSum(new int[]{0,0,0,0});
//        for(List<Integer> it:result4){
//            System.out.println(it+" ");
//        }
//        List<List<Integer>> result5 = threeSum.threeSum(new int[]{-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6});
//        for(List<Integer> it:result5){
//            System.out.println(it+" ");
//        }
        List<List<Integer>> result6 = threeSum.threeSum(new int[]{-1,0,1,2,-1,-4});
        for(List<Integer> it:result6){
            System.out.println(it+" ");
        }
    }
}
